home *** CD-ROM | disk | FTP | other *** search
/ Visual Cafe 3 / Visual Cafe 3.ISO / Vcafe / Main.bin / BigInteger.java < prev    next >
Text File  |  1998-11-04  |  50KB  |  1,465 lines
  1. /*
  2.  * @(#)BigInteger.java    1.9 98/10/28
  3.  *
  4.  * Copyright 1996-1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  * 
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.math;
  16.  
  17. import java.util.Random;
  18.  
  19. /**
  20.  * Immutable arbitrary-precision integers.  All operations behave as if
  21.  * BigIntegers were represented in two's-complement notation (like Java's
  22.  * primitive integer types).  BigIntegers provide analogues to all of Java's
  23.  * primitive integer operators, and all relevant static methods from
  24.  * java.lang.Math.  Additionally, BigIntegers provide operations for modular
  25.  * arithmetic, GCD calculation, primality testing, prime generation,
  26.  * single-bit manipulation, and a few other odds and ends.
  27.  *
  28.  * <P>Semantics of arithmetic operations exactly mimic those of java's integer
  29.  * arithmetic operators, as defined in The Java Language Specification.  For
  30.  * example, division by zero throws an ArithmeticException, and division of
  31.  * a negative by a positive yields a negative (or zero) remainder.  All of
  32.  * the details in the Spec concerning overflow are ignored, as BigIntegers
  33.  * are made as large as necessary to accommodate the results of an operation.
  34.  *
  35.  * <P>Semantics of shift operations extend those of Java's shift operators
  36.  * to allow for negative shift distances.  A right-shift with a negative
  37.  * shift distance results in a left shift, and vice-versa.  The unsigned
  38.  * right shift operator (>>>) is omitted, as this operation makes little
  39.  * sense in combination with the "infinite word size" abstraction provided
  40.  * by this class.
  41.  *
  42.  * <P>Semantics of bitwise logical operations are are exactly mimic those of
  43.  * Java's bitwise integer operators.  The Binary operators (and, or, xor)
  44.  * implicitly perform sign extension on the shorter of the two operands
  45.  * prior to performing the operation.
  46.  *
  47.  * <P>Comparison operations perform signed integer comparisons, analogous to
  48.  * those performed by java's relational and equality operators.
  49.  *
  50.  * <P>Modular arithmetic operations are provided to compute residues, perform
  51.  * exponentiation, and compute multiplicative inverses.  These methods always
  52.  * return a non-negative result, between 0 and (modulus - 1), inclusive.
  53.  *
  54.  * <P>Single-bit operations operate on a single bit of the two's-complement
  55.  * representation of their operand.  If necessary, the operand is sign
  56.  * extended so that it contains the designated bit.  None of the single-bit
  57.  * operations can produce a number with a different sign from the the
  58.  * BigInteger being operated on, as they affect only a single bit, and the
  59.  * "infinite word size" abstraction provided by this class ensures that there
  60.  * are infinitely many "virtual sign bits" preceding each BigInteger.
  61.  *
  62.  *
  63.  * @see BigDecimal
  64.  * @version     1.9, 98/10/29
  65.  * @author      Josh Bloch
  66.  */
  67. public class BigInteger extends Number {
  68.  
  69.     /*
  70.      * The number is internally stored in "minimal" sign-magnitude format
  71.      * (i.e., no BigIntegers have a leading zero byte in their magnitudes).
  72.      * Zero is represented with a signum of 0 (and a zero-length magnitude).
  73.      * Thus, there is exactly one representation for each value.
  74.      */
  75.     private int signum;
  76.     private byte[] magnitude;
  77.  
  78.     /*
  79.      * These "redundant fields" are initialized with recognizable nonsense
  80.      * values, and cached the first time they are needed (or never, if they
  81.      * aren't needed).
  82.      */
  83.     private int bitCount =  -1;
  84.     private int bitLength = -1;
  85.     private int firstNonzeroByteNum = -2;  /* Only used for negative numbers */
  86.     private int lowestSetBit = -2;
  87.  
  88.     //Constructors
  89.  
  90.     /**
  91.      * Translates a byte array containing the two's-complement representation
  92.      * of a (signed) integer into a BigInteger.  The input array is assumed to
  93.      * be big-endian (i.e., the most significant byte is in the [0] position).
  94.      * (The most significant bit of the most significant byte is the sign bit.)
  95.      * The array must contain at least one byte or a NumberFormatException
  96.      * will be thrown.
  97.      */
  98.     public BigInteger(byte[] val) throws NumberFormatException{
  99.     if (val.length == 0)
  100.         throw new NumberFormatException("Zero length BigInteger");
  101.  
  102.     if (val[0] < 0) {
  103.         magnitude = makePositive(val);
  104.         signum = -1;
  105.     } else {
  106.         magnitude = stripLeadingZeroBytes(val);
  107.         signum = (magnitude.length == 0 ? 0 : 1);
  108.     }
  109.     }
  110.  
  111.     /**
  112.      * Translates the sign-magnitude representation of an integer into a
  113.      * BigInteger.  The sign is represented as an integer signum value (-1 for
  114.      * negative, 0 for zero, 1 for positive).  The magnitude is represented
  115.      * as a big-endian byte array (i.e., the most significant byte is in the
  116.      * [0] position).  An invalid signum value or a 0 signum value coupled
  117.      * with a nonzero magnitude will result in a NumberFormatException.
  118.      * A zero length magnitude array is permissible, and will result in
  119.      * in a value of 0 (irrespective of the given signum value).
  120.      */
  121.     public BigInteger(int signum, byte[] magnitude)
  122.     throws NumberFormatException{
  123.     this.magnitude = stripLeadingZeroBytes(magnitude);
  124.  
  125.     if (signum < -1 || signum > 1)
  126.         throw(new NumberFormatException("Invalid signum value"));
  127.  
  128.     if (this.magnitude.length==0) {
  129.         this.signum = 0;
  130.     } else {
  131.         if (signum == 0)
  132.         throw(new NumberFormatException("signum-magnitude mismatch"));
  133.         this.signum = signum;
  134.     }
  135.     }
  136.     
  137.     /**
  138.      * Translates a string containing an optional minus sign followed by a
  139.      * sequence of one or more digits in the specified radix into a BigInteger.
  140.      * The character-to-digit mapping is provided by Character.digit.
  141.      * Any extraneous characters (including whitespace), or a radix outside
  142.      * the range from Character.MIN_RADIX(2) to Character.MAX_RADIX(36),
  143.      * inclusive, will result in a NumberFormatException.
  144.      */
  145.     public BigInteger(String val, int radix) throws NumberFormatException {
  146.     int cursor = 0, numDigits;
  147.  
  148.     if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
  149.         throw new NumberFormatException("Radix out of range");
  150.     if (val.length() == 0)
  151.         throw new NumberFormatException("Zero length BigInteger");
  152.  
  153.     /* Check for leading minus sign */
  154.     signum = 1;
  155.     if (val.charAt(0) == '-') {
  156.         if (val.length() == 1)
  157.         throw new NumberFormatException("Zero length BigInteger");
  158.         signum = -1;
  159.         cursor = 1;
  160.     }
  161.  
  162.     /* Skip leading zeros and compute number of digits in magnitude */
  163.     while (cursor<val.length() && val.charAt(cursor)==ZERO_CHAR)
  164.         cursor++;
  165.     if (cursor==val.length()) {
  166.         signum = 0;
  167.         magnitude = new byte[0];
  168.         return;
  169.     } else {
  170.         numDigits = val.length() - cursor;
  171.     }
  172.  
  173.     /* Process first (potentially short) digit group, if necessary */
  174.     int firstGroupLen = numDigits % digitsPerLong[radix];
  175.     if (firstGroupLen == 0)
  176.         firstGroupLen = digitsPerLong[radix];
  177.     String group = val.substring(cursor, cursor += firstGroupLen);
  178.     BigInteger tmp = valueOf(Long.parseLong(group, radix));
  179.  
  180.     /* Process remaining digit groups */
  181.     while (cursor < val.length()) {
  182.         group = val.substring(cursor, cursor += digitsPerLong[radix]);
  183.         long groupVal = Long.parseLong(group, radix);
  184.         if (groupVal <0)
  185.         throw new NumberFormatException("Illegal digit");
  186.         tmp = tmp.multiply(longRadix[radix]).add(valueOf(groupVal));
  187.     }
  188.  
  189.     magnitude = tmp.magnitude;
  190.     }
  191.  
  192.     /**
  193.      * Translates a string containing an optional minus sign followed by a
  194.      * sequence of one or more decimal digits into a BigInteger.  The
  195.      * character-to-digit mapping is provided by Character.digit.
  196.      * Any extraneous characters (including whitespace) will result in a
  197.      * NumberFormatException. 
  198.      */
  199.     public BigInteger(String val) throws NumberFormatException {
  200.     this(val, 10);
  201.     }
  202.  
  203.     /**
  204.      * Returns a random number uniformly distributed on [0, 2**numBits - 1]
  205.      * (assuming a fair source of random bits is provided in rndSrc).
  206.      * Note that this constructor always returns a non-negative BigInteger.
  207.      * Throws an IllegalArgumentException if numBits < 0.
  208.      */
  209.     public BigInteger(int numBits, Random rndSrc)
  210.     throws IllegalArgumentException {
  211.     this(1, randomBits(numBits, rndSrc));
  212.     }
  213.  
  214.     private static byte[] randomBits(int numBits, Random rndSrc)
  215.     throws IllegalArgumentException {
  216.     if (numBits < 0)
  217.         throw new IllegalArgumentException("numBits must be non-negative");
  218.     int numBytes = (numBits+7)/8;
  219.     byte[] randomBits = new byte[numBytes];
  220.  
  221.     /* Generate random bytes and mask out any excess bits */
  222.     if (numBytes > 0) {
  223.         rndSrc.nextBytes(randomBits);
  224.         int excessBits = 8*numBytes - numBits;
  225.         randomBits[0] &= (1 << (8-excessBits)) - 1;
  226.     }
  227.     return randomBits;
  228.     }
  229.  
  230.  
  231.     /**
  232.      * Returns a randomly selected BigInteger with the specified bitLength
  233.      * that is probably prime.  The certainty parameter is a measure of
  234.      * the uncertainty that the caller is willing to tolerate: the probability
  235.      * that the number is prime will exceed 1 - 1/2**certainty.  The execution
  236.      * time is proportional to the value of the certainty parameter.  The
  237.      * given random number generator is used to select candidates to be
  238.      * tested for primality.  Throws an ArithmeticException if bitLength < 2.
  239.      */
  240.     public BigInteger(int bitLength, int certainty, Random rnd) {
  241.     if (bitLength < 2)
  242.         throw new ArithmeticException("bitLength < 2");
  243.  
  244.     BigInteger p;
  245.     do {
  246.         /*
  247.          * Select a candidate of exactly the right length.  Note that
  248.          * Plumb's generator doesn't handle bitLength<=16 properly.
  249.          */
  250.         do {
  251.         p = new BigInteger(bitLength-1, rnd).setBit(bitLength-1);
  252.         p = (bitLength <= 16
  253.              ? (bitLength > 2 ? p.setBit(0) : p)
  254.              : new BigInteger(plumbGeneratePrime(p.magnitude), 1));
  255.         } while (p.bitLength() != bitLength);
  256.     } while (!p.isProbablePrime(certainty));
  257.  
  258.     signum = 1;
  259.     magnitude = p.magnitude;
  260.     }
  261.  
  262.  
  263.     /**
  264.      * This private constructor differs from its public cousin
  265.      * with the arguments reversed in two ways: it assumes that its
  266.      * arguments are correct, and it doesn't copy the magnitude array.
  267.      */
  268.     private BigInteger(byte[] magnitude, int signum) {
  269.     this.signum = (magnitude.length==0 ? 0 : signum);
  270.     this.magnitude = magnitude;
  271.     }
  272.  
  273.  
  274.     //Static Factory Methods
  275.  
  276.     /**
  277.      * Returns a BigInteger with the specified value.  This factory is provided
  278.      * in preference to a (long) constructor because it allows for reuse
  279.      * of frequently used BigIntegers (like 0 and 1), obviating the need for
  280.      * exported constants.
  281.      */
  282.     public static BigInteger valueOf(long val) {
  283.     /* If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant */
  284.     if (val == 0)
  285.         return ZERO;
  286.     if (val > 0 && val <= MAX_CONSTANT)
  287.         return posConst[(int) val];
  288.     else if (val < 0 && val >= -MAX_CONSTANT)
  289.         return negConst[(int) -val];
  290.  
  291.     /* Dump two's complement binary into valArray */
  292.     byte valArray[] = new byte[8];
  293.     for (int i=0; i<8; i++, val >>= 8)
  294.         valArray[7-i] = (byte)val;
  295.     return new BigInteger(valArray);
  296.     }
  297.  
  298.     private final static BigInteger ZERO = new BigInteger(new byte[0], 0);
  299.  
  300.     /**
  301.      * Initialize static constant array when class is loaded.
  302.      */
  303.     private final static int MAX_CONSTANT = 16;
  304.     private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
  305.     private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
  306.     static {
  307.     for (int i = 1; i <= MAX_CONSTANT; i++) {
  308.         byte[] magnitude = new byte[1];
  309.         magnitude[0] = (byte) i;
  310.         posConst[i] = new BigInteger(magnitude,  1);
  311.         negConst[i] = new BigInteger(magnitude, -1);
  312.     }
  313.     }
  314.  
  315.     /**
  316.      * Returns a BigInteger with the given two's complement representation.
  317.      * Assumes that the input array will not be modified (the returned
  318.      * BigInteger will reference the input array if feasible).
  319.      */
  320.     private static BigInteger valueOf(byte val[]) {
  321.     return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
  322.     }
  323.  
  324.  
  325.     // Arithmetic Operations
  326.  
  327.     /**
  328.      * Returns a BigInteger whose value is (this + val).
  329.      */
  330.     public BigInteger add(BigInteger val) throws ArithmeticException {
  331.     if (val.signum == 0)
  332.         return this;
  333.     else if (this.signum == 0)
  334.         return val;
  335.     else if (val.signum == signum)
  336.         return new BigInteger(plumbAdd(magnitude, val.magnitude), signum);
  337.     else if (this.signum < 0)
  338.         return plumbSubtract(val.magnitude, magnitude);
  339.     else  /* val.signum < 0 */
  340.         return plumbSubtract(magnitude, val.magnitude);
  341.     }
  342.  
  343.     /**
  344.      * Returns a BigInteger whose value is (this - val).
  345.      */
  346.     public BigInteger subtract(BigInteger val) {
  347.     return add(new BigInteger(val.magnitude, -val.signum));
  348.     }
  349.  
  350.     /**
  351.      * Returns a BigInteger whose value is (this * val).
  352.      */
  353.     public BigInteger multiply(BigInteger val) {
  354.  
  355.     if (val.signum == 0 || this.signum==0)
  356.         return ZERO;
  357.     else
  358.         return new BigInteger(plumbMultiply(magnitude, val.magnitude),
  359.                   signum * val.signum);
  360.     }
  361.  
  362.     /**
  363.      * Returns a BigInteger whose value is (this / val).  Throws an
  364.      * ArithmeticException if val == 0.
  365.      */
  366.     public BigInteger divide(BigInteger val) throws ArithmeticException {
  367.  
  368.     if (val.signum == 0)
  369.         throw new ArithmeticException("BigInteger divide by zero");
  370.     else if (this.signum == 0)
  371.         return ZERO;
  372.     else
  373.         return new BigInteger(plumbDivide(magnitude, val.magnitude),
  374.                   signum * val.signum);
  375.     }
  376.  
  377.     /**
  378.      * Returns a BigInteger whose value is (this % val).  Throws an
  379.      * ArithmeticException if val == 0.
  380.      */
  381.     public BigInteger remainder(BigInteger val) throws ArithmeticException {
  382.  
  383.     if (val.signum == 0)
  384.         throw new ArithmeticException("BigInteger divide by zero");
  385.     else if (this.signum == 0)
  386.         return ZERO;
  387.     else if (this.magnitude.length < val.magnitude.length)
  388.         return this; /*** WORKAROUND FOR BUG IN R1.1 OF PLUMB'S PKG ***/
  389.     else
  390.         return new BigInteger(plumbRemainder(magnitude,val.magnitude),
  391.                   signum);
  392.     }
  393.  
  394.     /**
  395.      * Returns an array of two BigIntegers. The first ([0]) element of
  396.      * the return value is the quotient (this / val), and the second ([1])
  397.      * element is the remainder (this % val).  Throws an ArithmeticException
  398.      * if val == 0.
  399.      */
  400.     public BigInteger[] divideAndRemainder(BigInteger val)
  401.     throws ArithmeticException {
  402.     BigInteger result[] = new BigInteger[2];
  403.  
  404.     if (val.signum == 0) {
  405.         throw new ArithmeticException("BigInteger divide by zero");
  406.     } else if (this.signum == 0) {
  407.         result[0] = result[1] = ZERO;
  408.     } else if (this.magnitude.length < val.magnitude.length) {
  409.         /*** WORKAROUND FOR A BUG IN R1.1 OF PLUMB'S PACKAGE ***/
  410.         result[0] = ZERO;
  411.         result[1] = this;
  412.     } else {
  413.         byte resultMagnitude[][] =
  414.         plumbDivideAndRemainder(magnitude, val.magnitude);
  415.         result[0] = new BigInteger(resultMagnitude[0], signum*val.signum);
  416.         result[1] = new BigInteger(resultMagnitude[1], signum);
  417.     }
  418.     return result;
  419.     }
  420.  
  421.     /**
  422.      * Returns a BigInteger whose value is (this ** exponent).  Throws
  423.      * an ArithmeticException if exponent < 0 (as the operation would yield
  424.      * a non-integer value). Note that exponent is an integer rather than
  425.      * a BigInteger.
  426.      */
  427.     public BigInteger pow(int exponent) throws ArithmeticException {
  428.     if (exponent < 0)
  429.         throw new ArithmeticException("Negative exponent");
  430.     if (signum==0)
  431.         return (exponent==0 ? ONE : this);
  432.  
  433.     /* Perform exponetiation using repeated squaring trick */
  434.     BigInteger result = valueOf(exponent<0 && (exponent&1)==1 ? -1 : 1);
  435.     BigInteger baseToPow2 = this;
  436.     while (exponent != 0) {
  437.         if ((exponent & 1)==1)
  438.         result = result.multiply(baseToPow2);
  439.         if ((exponent >>= 1) != 0)
  440.         baseToPow2 = new BigInteger(
  441.                     plumbSquare(baseToPow2.magnitude), 1);
  442.     }
  443.     return result;
  444.     }
  445.  
  446.     /**
  447.      * Returns a BigInteger whose value is the greatest common denominator
  448.      * of abs(this) and abs(val).  Returns 0 if this == 0 && val == 0.
  449.      */
  450.     public BigInteger gcd(BigInteger val) {
  451.     if (val.signum == 0)
  452.         return this.abs();
  453.     else if (this.signum == 0)
  454.         return val.abs();
  455.     else
  456.         return new BigInteger(plumbGcd(magnitude, val.magnitude), 1);
  457.     }
  458.  
  459.    /**
  460.     * Returns a BigInteger whose value is the absolute value of this
  461.     * number.
  462.     */
  463.     public BigInteger abs() {
  464.     return (signum >= 0 ? this : this.negate());
  465.     }
  466.  
  467.     /**
  468.      * Returns a BigInteger whose value is (-1 * this).
  469.      */
  470.     public BigInteger negate() {
  471.     return new BigInteger(this.magnitude, -this.signum);
  472.     }
  473.  
  474.     /**
  475.      * Returns the signum function of this number (i.e., -1, 0 or 1 as
  476.      * the value of this number is negative, zero or positive).
  477.      */
  478.     public int signum() {
  479.     return this.signum;
  480.     }
  481.  
  482.     // Modular Arithmetic Operations
  483.  
  484.     /**
  485.      * Returns a BigInteger whose value is this mod m. Throws an
  486.      * ArithmeticException if m <= 0.
  487.      */
  488.     public BigInteger mod(BigInteger m) {
  489.     if (m.signum <= 0)
  490.         throw new ArithmeticException("BigInteger: modulus not positive");
  491.  
  492.     BigInteger result = this.remainder(m);
  493.     return (result.signum >= 0 ? result : result.add(m));
  494.     }
  495.  
  496.     /**
  497.      * Returns a BigInteger whose value is (this ** exponent) mod m.  (If
  498.      * exponent == 1, the returned value is (this mod m).  If exponent < 0,
  499.      * the returned value is the modular multiplicative inverse of
  500.      * (this ** -exponent).)  Throws an ArithmeticException if m <= 0.
  501.      */
  502.     public BigInteger modPow(BigInteger exponent, BigInteger m) {
  503.     if (m.signum <= 0)
  504.         throw new ArithmeticException("BigInteger: modulus not positive");
  505.  
  506.     /* Workaround for a bug in Plumb: x^0 (y) dumps core for x != 0 */
  507.     if (exponent.signum == 0)
  508.         return ONE;
  509.  
  510.     boolean invertResult;
  511.     if ((invertResult = (exponent.signum < 0)))
  512.         exponent = exponent.negate();
  513.  
  514.     BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0 
  515.                ? this.mod(m) : this);
  516.     BigInteger result;
  517.     if (m.testBit(0)) { /* Odd modulus: just pass it on to Plumb */
  518.         result = new BigInteger
  519.          (plumbModPow(base.magnitude, exponent.magnitude, m.magnitude), 1);
  520.     } else {
  521.         /*
  522.          * Even modulus.  Plumb only supports odd, so tear it into
  523.          * "odd part" (m1) and power of two (m2), use Plumb to exponentiate
  524.          * mod m1, manually exponentiate mod m2, and use Chinese Remainder
  525.          * Theorem to combine results.
  526.          */
  527.  
  528.         /* Tear m apart into odd part (m1) and power of 2 (m2) */
  529.         int p = m.getLowestSetBit();      /* Max pow of 2 that divides m */
  530.         BigInteger m1 = m.shiftRight(p);  /* m/2**p */
  531.         BigInteger m2 = ONE.shiftLeft(p); /* 2**p */
  532.  
  533.         /* Caculate (base ** exponent) mod m1 */
  534.         BigInteger a1 = new BigInteger
  535.          (plumbModPow(base.magnitude, exponent.magnitude, m1.magnitude),1);
  536.  
  537.         /* Caculate (this ** exponent) mod m2 */
  538.         BigInteger a2 = base.modPow2(exponent, p);
  539.  
  540.         /* Combine results using Chinese Remainder Theorem */
  541.         BigInteger y1 = m2.modInverse(m1);
  542.         BigInteger y2 = m1.modInverse(m2);
  543.         result = a1.multiply(m2).multiply(y1).add
  544.             (a2.multiply(m1).multiply(y2)).mod(m);
  545.     }
  546.  
  547.     return (invertResult ? result.modInverse(m) : result);
  548.     }
  549.     
  550.     /**
  551.      * Returns (this ** exponent) mod(2**p)
  552.      */
  553.     private BigInteger modPow2(BigInteger exponent, int p) {
  554.     /*
  555.      * Perform exponetiation using repeated squaring trick, chopping off
  556.      * high order bits as indicated by modulus.
  557.      */
  558.     BigInteger result = valueOf(1);
  559.     BigInteger baseToPow2 = this.mod2(p);
  560.     while (exponent.signum != 0) {
  561.         if (exponent.testBit(0))
  562.         result = result.multiply(baseToPow2).mod2(p);
  563.         exponent = exponent.shiftRight(1);
  564.         if (exponent.signum != 0)
  565.         baseToPow2 = new BigInteger(
  566.                    plumbSquare(baseToPow2.magnitude), 1).mod2(p);
  567.     }
  568.     return result;
  569.     }
  570.  
  571.     /**
  572.      * Returns this mod(2**p).  Assumes that this BigInteger >= 0 and p > 0.
  573.      */
  574.     private BigInteger mod2(int p) {
  575.     if (bitLength() <= p)
  576.         return this;
  577.  
  578.     /* Copy remaining bytes of magnitude */
  579.     int numBytes = (p+7)/8;
  580.     byte[] mag = new byte[numBytes];
  581.     for (int i=0; i<numBytes; i++)
  582.         mag[i] = magnitude[i + (magnitude.length - numBytes)];
  583.  
  584.     /* Mask out any excess bits */
  585.     int excessBits = 8*numBytes - p;
  586.     mag[0] &= (1 << (8-excessBits)) - 1;
  587.  
  588.     return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
  589.     }
  590.  
  591.     /**
  592.      * Returns modular multiplicative inverse of this, mod m.  Throws an
  593.      * ArithmeticException if m <= 0 or this has no multiplicative inverse
  594.      * mod m (i.e., gcd(this, m) != 1).
  595.      */
  596.     public BigInteger modInverse(BigInteger m) throws ArithmeticException {
  597.     if (m.signum != 1)
  598.         throw new ArithmeticException("BigInteger: modulus not positive");
  599.  
  600.     /* Calculate (this mod m) */
  601.     BigInteger modVal = this.remainder(m);
  602.     if (modVal.signum < 0)
  603.         modVal = modVal.add(m);
  604.     if (!modVal.gcd(m).equals(ONE))
  605.         throw new ArithmeticException("BigInteger not invertible");
  606.  
  607.     return new BigInteger(plumbModInverse(modVal.magnitude,m.magnitude),1);
  608.     }
  609.  
  610.  
  611.     // Shift Operations
  612.  
  613.     /**
  614.      * Returns a BigInteger whose value is (this << n).  (Computes
  615.      * floor(this * 2**n).)
  616.      */
  617.     public BigInteger shiftLeft(int n) {
  618.     if (n==0)
  619.         return this;
  620.     if (n<0)
  621.         return shiftRight(-n);
  622.  
  623.     int nBytes = n/8;
  624.     int nBits = n%8;
  625.  
  626.     byte result[] = new byte[(bitLength()+n)/8+1];
  627.     if (nBits == 0) {
  628.         for (int i=nBytes; i<result.length; i++)
  629.         result[result.length-1-i] = getByte(i-nBytes);
  630.     } else {
  631.         for (int i=nBytes; i<result.length; i++)
  632.         result[result.length-1-i] = (byte)
  633.             ((getByte(i-nBytes) << nBits)
  634.             | (i==nBytes ? 0
  635.                : ((getByte(i-nBytes-1)&0xff) >> (8-nBits))));
  636.     }
  637.  
  638.     return valueOf(result);
  639.     }
  640.  
  641.     /**
  642.      * Returns a BigInteger whose value is (this >> n).  Sign extension is
  643.      * performed.  (Computes floor(this / 2**n).)
  644.      */
  645.     public BigInteger shiftRight(int n) {
  646.     if (n==0)
  647.         return this;
  648.     if (n<0)
  649.         return shiftLeft(-n);
  650.     if (n >= bitLength())
  651.         return (signum<0 ? valueOf(-1) : ZERO);
  652.  
  653.     int nBytes = n/8;
  654.     int nBits = n%8;
  655.  
  656.     byte result[] = new byte[(bitLength-n)/8+1];
  657.     if (nBits == 0) {
  658.         for (int i=0; i<result.length; i++)
  659.         result[result.length-1-i] = getByte(nBytes+i);
  660.     } else {
  661.         for (int i=0; i<result.length; i++)
  662.         result[result.length-1-i] = (byte)
  663.         ((getByte(nBytes+i+1)<<8 | (getByte(nBytes+i)&0xff)) >> nBits);
  664.     }
  665.  
  666.     return valueOf(result);
  667.     }
  668.  
  669.  
  670.     // Bitwise Operations
  671.  
  672.     /**
  673.      * Returns a BigInteger whose value is (this & val).  (This method
  674.      * returns a negative number iff this and val are both negative.)
  675.      */
  676.     public BigInteger and(BigInteger val) {
  677.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  678.     for (int i=0; i<result.length; i++)
  679.         result[i] = (byte) (getByte(result.length-i-1)
  680.                 & val.getByte(result.length-i-1));
  681.  
  682.     return valueOf(result);
  683.     }
  684.  
  685.     /**
  686.      * Returns a BigInteger whose value is (this | val).  (This method
  687.      * returns a negative number iff either this or val is negative.)
  688.      */
  689.     public BigInteger or(BigInteger val) {
  690.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  691.     for (int i=0; i<result.length; i++)
  692.         result[i] = (byte) (getByte(result.length-i-1)
  693.                 | val.getByte(result.length-i-1));
  694.  
  695.     return valueOf(result);
  696.     }
  697.  
  698.     /**
  699.      * Returns a BigInteger whose value is (this ^ val).  (This method
  700.      * returns a negative number iff exactly one of this and val are 
  701.      * negative.)
  702.      */
  703.     public BigInteger xor(BigInteger val) {
  704.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  705.     for (int i=0; i<result.length; i++)
  706.         result[i] = (byte) (getByte(result.length-i-1)
  707.                 ^ val.getByte(result.length-i-1));
  708.  
  709.     return valueOf(result);
  710.     }
  711.  
  712.     /**
  713.      * Returns a BigInteger whose value is (~this).  (This method returns
  714.      * a negative value iff this number is non-negative.)
  715.      */
  716.     public BigInteger not() {
  717.     byte[] result = new byte[byteLength()];
  718.     for (int i=0; i<result.length; i++)
  719.         result[i] = (byte) ~getByte(result.length-i-1);
  720.  
  721.     return valueOf(result);
  722.     }
  723.  
  724.     /**
  725.      * Returns a BigInteger whose value is (this & ~val).  This method,
  726.      * which is equivalent to and(val.not()), is provided as a convenience
  727.      * for masking operations.  (This method returns a negative number iff
  728.      * this is negative and val is positive.)
  729.      */
  730.     public BigInteger andNot(BigInteger val) {
  731.     byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
  732.     for (int i=0; i<result.length; i++)
  733.         result[i] = (byte) (getByte(result.length-i-1)
  734.                 & ~val.getByte(result.length-i-1));
  735.  
  736.     return valueOf(result);
  737.     }
  738.  
  739.  
  740.     // Single Bit Operations
  741.  
  742.     /**
  743.      * Returns true iff the designated bit is set. (Computes
  744.      * ((this & (1<<n)) != 0).)  Throws an ArithmeticException if n < 0.
  745.      */
  746.     public boolean testBit(int n) throws ArithmeticException {
  747.     if (n<0)
  748.         throw new ArithmeticException("Negative bit address");
  749.  
  750.     return (getByte(n/8) & (1 << (n%8))) != 0;
  751.     }
  752.  
  753.     /**
  754.      * Returns a BigInteger whose value is equivalent to this number
  755.      * with the designated bit set.  (Computes (this | (1<<n)).)
  756.      * Throws an ArithmeticException if n < 0.
  757.      */
  758.     public BigInteger setBit(int n) throws ArithmeticException {
  759.     if (n<0)
  760.         throw new ArithmeticException("Negative bit address");
  761.  
  762.     int byteNum = n/8;
  763.     byte[] result = new byte[Math.max(byteLength(), byteNum+2)];
  764.  
  765.     for (int i=0; i<result.length; i++)
  766.         result[result.length-i-1] = getByte(i);
  767.  
  768.     result[result.length-byteNum-1] |= (1 << (n%8));
  769.  
  770.     return valueOf(result);
  771.     }
  772.  
  773.     /**
  774.      * Returns a BigInteger whose value is equivalent to this number
  775.      * with the designated bit cleared. (Computes (this & ~(1<<n)).)
  776.      * Throws an ArithmeticException if n < 0.
  777.      */
  778.     public BigInteger clearBit(int n) throws ArithmeticException {
  779.     if (n<0)
  780.         throw new ArithmeticException("Negative bit address");
  781.  
  782.     int byteNum = n/8;
  783.     byte[] result = new byte[Math.max(byteLength(), (n+1)/8+1)];
  784.  
  785.     for (int i=0; i<result.length; i++)
  786.         result[result.length-i-1] = getByte(i);
  787.  
  788.     result[result.length-byteNum-1] &= ~(1 << (n%8));
  789.  
  790.     return valueOf(result);
  791.     }
  792.  
  793.     /**
  794.      * Returns a BigInteger whose value is equivalent to this number
  795.      * with the designated bit flipped.  (Computes (this ^ (1<<n)).)
  796.      * Throws an ArithmeticException if n < 0.
  797.      */
  798.     public BigInteger flipBit(int n) throws ArithmeticException {
  799.     if (n<0)
  800.         throw new ArithmeticException("Negative bit address");
  801.  
  802.     int byteNum = n/8;
  803.     byte[] result = new byte[Math.max(byteLength(), byteNum+2)];
  804.  
  805.     for (int i=0; i<result.length; i++)
  806.         result[result.length-i-1] = getByte(i);
  807.  
  808.     result[result.length-byteNum-1] ^= (1 << (n%8));
  809.  
  810.     return valueOf(result);
  811.     }
  812.  
  813.     /**
  814.      * Returns the index of the rightmost (lowest-order) one bit in this
  815.      * number (i.e., the number of zero bits to the right of the rightmost
  816.      * one bit).  Returns -1 if this number contains no one bits.
  817.      * (Computes (this==0? -1 : log2(this & -this)).)
  818.      */
  819.     public int getLowestSetBit() {
  820.     /*
  821.      * Initialize lowestSetBit field the first time this method is
  822.      * executed. This method depends on the atomicity of int modifies;
  823.      * without this guarantee, it would have to be synchronized.
  824.      */
  825.     if (lowestSetBit == -2) {
  826.         if (signum == 0) {
  827.         lowestSetBit = -1;
  828.         } else {
  829.         /* Search for lowest order nonzero byte */
  830.         int i;
  831.         byte b;
  832.         for (i=0; (b = getByte(i))==0; i++)
  833.             ;
  834.         lowestSetBit = 8*i + trailingZeroCnt[b & 0xFF];
  835.         }
  836.     }
  837.     return lowestSetBit;
  838.     }
  839.  
  840.  
  841.     // Miscellaneous Bit Operations
  842.  
  843.     /**
  844.      * Returns the number of bits in the minimal two's-complement
  845.      * representation of this number, *excluding* a sign bit, i.e.,
  846.      * (ceil(log2(this < 0 ? -this : this + 1))).  (For positive
  847.      * numbers, this is equivalent to the number of bits in the
  848.      * ordinary binary representation.)
  849.      */
  850.     public int bitLength() {
  851.     /*
  852.      * Initialize bitLength field the first time this method is executed.
  853.      * This method depends on the atomicity of int modifies; without
  854.      * this guarantee, it would have to be synchronized.
  855.      */
  856.     if (bitLength == -1) {
  857.         if (signum == 0) {
  858.         bitLength = 0;
  859.         } else {
  860.         /* Calculate the bit length of the magnitude */
  861.         int magBitLength = 8*(magnitude.length-1)
  862.                        + bitLen[magnitude[0] & 0xff];
  863.  
  864.         if (signum < 0) {
  865.             /* Check if magnitude is a power of two */
  866.             boolean pow2 = (bitCnt[magnitude[0]&0xff] == 1);
  867.             for(int i=1; i<magnitude.length && pow2; i++)
  868.             pow2 = (magnitude[i]==0);
  869.  
  870.             bitLength = (pow2 ? magBitLength-1 : magBitLength);
  871.         } else {
  872.             bitLength = magBitLength;
  873.         }
  874.         }
  875.     }
  876.     return bitLength;
  877.     }
  878.  
  879.     /*
  880.      * bitLen[i] is the number of bits in the binary representaion of i.
  881.      */
  882.     private final static byte bitLen[] = {
  883.     0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
  884.     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  885.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  886.     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  887.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  888.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  889.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  890.     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  891.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  892.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  893.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  894.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  895.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  896.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  897.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
  898.     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};
  899.  
  900.     /**
  901.      * Returns the number of bits in the two's complement representation
  902.      * of this number that differ from its sign bit.  This method is
  903.      * useful when implementing bit-vector style sets atop BigIntegers.
  904.      */
  905.     public int bitCount() {
  906.     /*
  907.      * Initialize bitCount field the first time this method is executed.
  908.      * This method depends on the atomicity of int modifies; without
  909.      * this guarantee, it would have to be synchronized.
  910.      */
  911.     if (bitCount == -1) {
  912.         /* Count the bits in the magnitude */
  913.         int magBitCount = 0;
  914.         for (int i=0; i<magnitude.length; i++)
  915.         magBitCount += bitCnt[magnitude[i] & 0xff];
  916.  
  917.         if (signum < 0) {
  918.         /* Count the trailing zeros in the magnitude */
  919.         int magTrailingZeroCount = 0, j;
  920.         for (j=magnitude.length-1; magnitude[j]==0; j--)
  921.             magTrailingZeroCount += 8;
  922.         magTrailingZeroCount += trailingZeroCnt[magnitude[j] & 0xff];
  923.  
  924.         bitCount = magBitCount + magTrailingZeroCount - 1;
  925.         } else {
  926.         bitCount = magBitCount;
  927.         }
  928.     }
  929.     return bitCount;
  930.     }
  931.  
  932.     /*
  933.      * bitCnt[i] is the number of 1 bits in the binary representation of i.
  934.      */
  935.     private final static byte bitCnt[] = {
  936.     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  937.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  938.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  939.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  940.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  941.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  942.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  943.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  944.     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  945.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  946.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  947.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  948.     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  949.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  950.     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  951.     4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
  952.  
  953.     /*
  954.      * trailingZeroCnt[i] is the number of trailing zero bits in the binary
  955.      * representaion of i.
  956.      */
  957.     private final static byte trailingZeroCnt[] = {
  958.     8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  959.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  960.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  961.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  962.     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  963.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  964.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  965.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  966.     7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  967.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  968.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  969.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  970.     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  971.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  972.     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  973.     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
  974.  
  975.  
  976.  
  977.     // Primality Testing
  978.  
  979.     /**
  980.      * Returns true if this BigInteger is probably prime, false if it's
  981.      * definitely composite.  The certainty parameter is a measure 
  982.      * of the uncertainty that the caller is willing to tolerate:
  983.      * the method returns true if the probability that this number is
  984.      * is prime exceeds 1 - 1/2**certainty.  The execution time is
  985.      * proportional to the value of the certainty parameter.
  986.      */
  987.     public boolean isProbablePrime(int certainty) {
  988.     /*
  989.      * This test is taken from the DSA spec.
  990.      */
  991.     int n = certainty/2;
  992.     if (n <= 0)
  993.         return true;
  994.     BigInteger w = this.abs();
  995.     if (w.equals(TWO))
  996.         return true;
  997.     if (!w.testBit(0) || w.equals(ONE))
  998.         return false;
  999.  
  1000.     /* Find a and m such that m is odd and w == 1 + 2**a * m */
  1001.     BigInteger m = w.subtract(ONE);
  1002.     int a = m.getLowestSetBit();
  1003.     m = m.shiftRight(a);
  1004.  
  1005.     /* Do the tests */
  1006.     Random rnd = new Random();
  1007.     for(int i=0; i<n; i++) {
  1008.         /* Generate a uniform random on (1, w) */
  1009.         BigInteger b;
  1010.         do {
  1011.         b = new BigInteger(w.bitLength(), rnd);
  1012.         } while (b.compareTo(ONE) <= 0 || b.compareTo(w) >= 0);
  1013.  
  1014.         int j = 0;
  1015.         BigInteger z = b.modPow(m, w);
  1016.         while(!((j==0 && z.equals(ONE)) || z.equals(w.subtract(ONE)))) {
  1017.         if (j>0 && z.equals(ONE) || ++j==a)
  1018.             return false;
  1019.         z = z.modPow(TWO, w);
  1020.         }
  1021.     }
  1022.     return true;
  1023.     }
  1024.  
  1025.  
  1026.     // Comparison Operations
  1027.  
  1028.     /**
  1029.      * Returns -1, 0 or 1 as this number is less than, equal to, or
  1030.      * greater than val.  This method is provided in preference to
  1031.      * individual methods for each of the six boolean comparison operators
  1032.      * (<, ==, >, >=, !=, <=).  The suggested idiom for performing these
  1033.      * comparisons is:  (x.compareTo(y) <op> 0), where <op> is one of the
  1034.      * six comparison operators.
  1035.      */
  1036.     public int compareTo(BigInteger val) {
  1037.     return (signum==val.signum
  1038.         ? signum*byteArrayCmp(magnitude, val.magnitude)
  1039.         : (signum>val.signum ? 1 : -1));
  1040.     }
  1041.  
  1042.     /*
  1043.      * Returns -1, 0 or +1 as big-endian unsigned byte array arg1 is
  1044.      * <, == or > arg2.
  1045.      */
  1046.     private static int byteArrayCmp(byte[] arg1, byte[] arg2) {
  1047.     if (arg1.length < arg2.length)
  1048.         return -1;
  1049.     if (arg1.length > arg2.length)
  1050.         return 1;
  1051.  
  1052.     /* Argument lengths are equal; compare the values */
  1053.     for (int i=0; i<arg1.length; i++) {
  1054.         int b1 = arg1[i] & 0xff;
  1055.         int b2 = arg2[i] & 0xff;
  1056.         if (b1 < b2)
  1057.         return -1;
  1058.         if (b1 > b2)
  1059.         return 1;
  1060.     }
  1061.     return 0;
  1062.     }
  1063.  
  1064.     /**
  1065.      * Returns true iff x is a BigInteger whose value is equal to this number.
  1066.      * This method is provided so that BigIntegers can be used as hash keys.
  1067.      */
  1068.     public boolean equals(Object x) {
  1069.     if (!(x instanceof BigInteger))
  1070.         return false;
  1071.     BigInteger xInt = (BigInteger) x;
  1072.  
  1073.     if (xInt.signum != signum || xInt.magnitude.length != magnitude.length)
  1074.         return false;
  1075.  
  1076.     /* This test is just an optimization, which may or may not help */
  1077.     if (xInt == this)
  1078.         return true;
  1079.  
  1080.     for (int i=0; i<magnitude.length; i++)
  1081.         if (xInt.magnitude[i] != magnitude[i])
  1082.         return false;
  1083.  
  1084.     return true;
  1085.     }
  1086.  
  1087.     /**
  1088.      * Returns the BigInteger whose value is the lesser of this and val.
  1089.      * If the values are equal, either may be returned.
  1090.      */
  1091.     public BigInteger min(BigInteger val) {
  1092.     return (compareTo(val)<0 ? this : val);
  1093.     }
  1094.  
  1095.     /**
  1096.      * Returns the BigInteger whose value is the greater of this and val.
  1097.      * If the values are equal, either may be returned.
  1098.      */
  1099.     public BigInteger max(BigInteger val) {
  1100.     return (compareTo(val)>0 ? this : val);
  1101.     }
  1102.  
  1103.  
  1104.     // Hash Function
  1105.  
  1106.     /**
  1107.      * Computes a hash code for this object.
  1108.      */
  1109.     public int hashCode() {
  1110.     int hashCode = 0;
  1111.  
  1112.     for (int i=0; i<magnitude.length; i++)
  1113.         hashCode = 37*hashCode + (magnitude[i] & 0xff);
  1114.  
  1115.     return hashCode * signum;
  1116.     }
  1117.  
  1118.     // Format Converters
  1119.  
  1120.     /**
  1121.      * Returns the string representation of this number in the given radix.
  1122.      * If the radix is outside the range from Character.MIN_RADIX(2) to
  1123.      * Character.MAX_RADIX(36) inclusive, it will default to 10 (as is the
  1124.      * case for Integer.toString).  The digit-to-character mapping provided
  1125.      * by Character.forDigit is used, and a minus sign is prepended if
  1126.      * appropriate.  (This representation is compatible with the (String, int)
  1127.      * constructor.)
  1128.      */
  1129.     public String toString(int radix) {
  1130.     if (signum == 0)
  1131.         return "0";
  1132.     if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
  1133.         radix = 10;
  1134.  
  1135.     /* Compute upper bound on number of digit groups and allocate space */
  1136.     int maxNumDigitGroups = (magnitude.length + 6)/7;
  1137.     String digitGroup[] = new String[maxNumDigitGroups];
  1138.  
  1139.     /* Translate number to string, a digit group at a time */
  1140.     BigInteger tmp = this.abs();
  1141.     int numGroups = 0;
  1142.     while (tmp.signum != 0) {
  1143.         BigInteger b[] = tmp.divideAndRemainder(longRadix[radix]);
  1144.         digitGroup[numGroups++] = Long.toString(b[1].longValue(), radix);
  1145.         tmp = b[0];
  1146.     }
  1147.  
  1148.     /* Put sign (if any) and first digit group into result buffer */
  1149.     StringBuffer buf = new StringBuffer(numGroups*digitsPerLong[radix]+1);
  1150.     if (signum<0)
  1151.         buf.append('-');
  1152.     buf.append(digitGroup[numGroups-1]);
  1153.  
  1154.     /* Append remaining digit groups padded with leading zeros */
  1155.     for (int i=numGroups-2; i>=0; i--) {
  1156.         /* Prepend (any) leading zeros for this digit group */
  1157.         int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
  1158.         if (numLeadingZeros != 0)
  1159.         buf.append(zeros[numLeadingZeros]);
  1160.         buf.append(digitGroup[i]);
  1161.     }
  1162.  
  1163.     return buf.toString();
  1164.     }
  1165.  
  1166.     /* zero[i] is a string of i consecutive zeros. */
  1167.     private static String zeros[] = new String[64];
  1168.     static {
  1169.     zeros[63] =
  1170.         "000000000000000000000000000000000000000000000000000000000000000";
  1171.     for (int i=0; i<63; i++)
  1172.         zeros[i] = zeros[63].substring(0, i);
  1173.     }
  1174.  
  1175.     /**
  1176.      * Returns the string representation of this number, radix 10.  The
  1177.      * digit-to-character mapping provided by Character.forDigit is used,
  1178.      * and a minus sign is prepended if appropriate.  (This representation
  1179.      * is compatible with the (String) constructor, and allows for string
  1180.      * concatenation with Java's + operator.)
  1181.      */
  1182.     public String toString() {
  1183.     return toString(10);
  1184.     }
  1185.  
  1186.     /**
  1187.      * Returns the two's-complement representation of this number.  The array
  1188.      * is big-endian (i.e., the most significant byte is in the [0] position).
  1189.      * The array contains the minimum number of bytes required to represent
  1190.      * the number (ceil((this.bitLength() + 1)/8)).  (This representation is
  1191.      * compatible with the (byte[]) constructor.) 
  1192.      */
  1193.     public byte[] toByteArray() {
  1194.     byte[] result = new byte[byteLength()];
  1195.     for(int i=0; i<result.length; i++)
  1196.         result[i] = getByte(result.length-i-1);
  1197.  
  1198.     return result;
  1199.     }
  1200.  
  1201.     /**
  1202.      * Converts this number to an int.  Standard narrowing primitive conversion
  1203.      * as per The Java Language Specification.
  1204.      */
  1205.     public int intValue() {
  1206.     int result = 0;
  1207.  
  1208.     for (int i=3; i>=0; i--)
  1209.         result = (result << 8) + (getByte(i) & 0xff);
  1210.     return result;
  1211.     }
  1212.  
  1213.     /**
  1214.      * Converts this number to a long.  Standard narrowing primitive conversion
  1215.      * as per The Java Language Specification.
  1216.      */
  1217.     public long longValue() {
  1218.     long result = 0;
  1219.  
  1220.     for (int i=7; i>=0; i--)
  1221.         result = (result << 8) + (getByte(i) & 0xff);
  1222.     return result;
  1223.     }
  1224.  
  1225.     /**
  1226.      * Converts this number to a float.  Similar to the double-to-float
  1227.      * narrowing primitive conversion defined in The Java Language
  1228.      * Specification: if the number has too great a magnitude to represent
  1229.      * as a float, it will be converted to infinity or negative infinity,
  1230.      * as appropriate.
  1231.      */
  1232.     public float floatValue() {
  1233.     /* Somewhat inefficient, but guaranteed to work. */
  1234.     return Float.valueOf(this.toString()).floatValue();
  1235.     }
  1236.  
  1237.     /**
  1238.      * Converts the number to a double.  Similar to the double-to-float
  1239.      * narrowing primitive conversion defined in The Java Language
  1240.      * Specification: if the number has too great a magnitude to represent
  1241.      * as a double, it will be converted to infinity or negative infinity,
  1242.      * as appropriate.
  1243.      */
  1244.     public double doubleValue() {
  1245.     /* Somewhat inefficient, but guaranteed to work. */
  1246.     return Double.valueOf(this.toString()).doubleValue();
  1247.     }
  1248.  
  1249.     static {
  1250.     System.loadLibrary("math");
  1251.     plumbInit();
  1252.     }
  1253.  
  1254.  
  1255.     private final static BigInteger ONE = valueOf(1);
  1256.     private final static BigInteger TWO = valueOf(2);
  1257.  
  1258.     private final static char ZERO_CHAR = Character.forDigit(0, 2);
  1259.  
  1260.     /**
  1261.      * Returns a copy of the input array stripped of any leading zero bytes.
  1262.      */
  1263.     static private byte[] stripLeadingZeroBytes(byte a[]) {
  1264.     int keep;
  1265.     
  1266.     /* Find first nonzero byte */
  1267.     for (keep=0; keep<a.length && a[keep]==0; keep++)
  1268.         ;
  1269.  
  1270.     /* Allocate new array and copy relevant part of input array */
  1271.     byte result[] = new byte[a.length - keep];
  1272.     for (int i = keep; i<a.length; i++)
  1273.         result[i - keep] = a[i];
  1274.  
  1275.     return result;
  1276.     }
  1277.  
  1278.     /**
  1279.      * Takes an array a representing a negative 2's-complement number and
  1280.      * returns the minimal (no leading zero bytes) unsigned whose value is -a.
  1281.      */
  1282.     static private byte[] makePositive(byte a[]) {
  1283.     int keep, j;
  1284.  
  1285.     /* Find first non-sign (0xff) byte of input */
  1286.     for (keep=0; keep<a.length && a[keep]==-1; keep++)
  1287.         ;
  1288.  
  1289.     /* Allocate output array.  If all non-sign bytes are 0x00, we must
  1290.      * allocate space for one extra output byte. */
  1291.     for (j=keep; j<a.length && a[j]==0; j++)
  1292.         ;
  1293.     int extraByte = (j==a.length ? 1 : 0);
  1294.     byte result[] = new byte[a.length - keep + extraByte];
  1295.  
  1296.     /* Copy one's complement of input into into output, leaving extra
  1297.      * byte (if it exists) == 0x00 */
  1298.     for (int i = keep; i<a.length; i++)
  1299.         result[i - keep + extraByte] = (byte) ~a[i];
  1300.  
  1301.     /* Add one to one's complement to generate two's complement */
  1302.     for (int i=result.length-1; ++result[i]==0; i--)
  1303.         ;
  1304.  
  1305.     return result;
  1306.     }
  1307.  
  1308.     /*
  1309.      * The following two arrays are used for fast String conversions.  Both
  1310.      * are indexed by radix.  The first is the number of digits of the given
  1311.      * radix that can fit in a Java long without "going negative", i.e., the
  1312.      * highest integer n such that radix ** n < 2 ** 63.  The second is the
  1313.      * "long radix" that tears each number into "long digits", each of which
  1314.      * consists of the number of digits in the corresponding element in
  1315.      * digitsPerLong (longRadix[i] = i ** digitPerLong[i]).  Both arrays have
  1316.      * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
  1317.      * used.
  1318.      */
  1319.  
  1320.     private static int digitsPerLong[] = {0, 0,
  1321.     62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
  1322.     14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
  1323.  
  1324.     private static BigInteger longRadix[] = {null, null,
  1325.         valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
  1326.     valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
  1327.     valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
  1328.         valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
  1329.     valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
  1330.     valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
  1331.     valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
  1332.     valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
  1333.     valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
  1334.     valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
  1335.     valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
  1336.     valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
  1337.     valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
  1338.     valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
  1339.     valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
  1340.     valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
  1341.     valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
  1342.     valueOf(0x41c21cb8e1000000L)};
  1343.  
  1344.  
  1345.     /**
  1346.      * These routines provide access to the two's complement representation
  1347.      * of BigIntegers.
  1348.      */
  1349.  
  1350.     /**
  1351.      * Returns the length of the two's complement representation in bytes,
  1352.      * including space for at least one sign bit, 
  1353.      */
  1354.     private int byteLength() {
  1355.     return bitLength()/8 + 1;
  1356.     }
  1357.  
  1358.     /* Returns sign bit */
  1359.     private int signBit() {
  1360.     return (signum < 0 ? 1 : 0);
  1361.     }
  1362.  
  1363.     /* Returns a byte of sign bits */
  1364.     private byte signByte() {
  1365.     return (byte) (signum < 0 ? -1 : 0);
  1366.     }
  1367.  
  1368.     /**
  1369.      * Returns the specified byte of the little-endian two's complement
  1370.      * representation (byte 0 is the LSB).  The byte number can be arbitrarily
  1371.      * high (values are logically preceded by infinitely many sign bytes).
  1372.      */
  1373.     private byte getByte(int n) {
  1374.     if (n >= magnitude.length)
  1375.         return signByte();
  1376.  
  1377.     byte magByte = magnitude[magnitude.length-n-1];
  1378.  
  1379.     return (byte) (signum >= 0 ? magByte :
  1380.                (n <= firstNonzeroByteNum() ? -magByte : ~magByte));
  1381.     }
  1382.  
  1383.     /**
  1384.      * Returns the index of the first nonzero byte in the little-endian 
  1385.      * binary representation of the magnitude (byte 0 is the LSB).  If
  1386.      * the magnitude is zero, return value is undefined.
  1387.      */
  1388.  
  1389.      private int firstNonzeroByteNum() {
  1390.     /*
  1391.      * Initialize bitCount field the first time this method is executed.
  1392.      * This method depends on the atomicity of int modifies; without
  1393.      * this guarantee, it would have to be synchronized.
  1394.      */
  1395.     if (firstNonzeroByteNum == -2) {
  1396.         /* Search for the first nonzero byte */
  1397.         int i;
  1398.         for (i=magnitude.length-1; i>=0 && magnitude[i]==0; i--)
  1399.         ;
  1400.         firstNonzeroByteNum = magnitude.length-i-1;
  1401.     }
  1402.     return firstNonzeroByteNum;
  1403.     }
  1404.  
  1405.  
  1406.     /**
  1407.      * Native method wrappers for Colin Plumb's big positive integer package.
  1408.      * Each of these wrappers (except for plumbInit) behaves as follows:
  1409.      *
  1410.      *     1) Translate input arguments from java byte arrays into plumbNums.
  1411.      *
  1412.      *  2) Perform the requested computation.
  1413.      *
  1414.      *  3) Translate result(s) into Java byte array(s).  (The subtract
  1415.      *       operation translates its result into a BigInteger, as its result
  1416.      *       is, effectively, signed.)
  1417.      *
  1418.      *    4) Deallocate all of the plumbNums.
  1419.      *
  1420.      *  5) Return the resulting Java array(s) (or, in the case of subtract,
  1421.      *       BigInteger).
  1422.      */
  1423.  
  1424.     private static native void plumbInit();
  1425.     private static native byte[] plumbAdd(byte[] a, byte[] b);
  1426.     private static native BigInteger plumbSubtract(byte[] a, byte[] b);
  1427.     private static native byte[] plumbMultiply(byte[] a, byte[] b);
  1428.     private static native byte[] plumbDivide(byte[] a, byte[] b);
  1429.     private static native byte[] plumbRemainder(byte[] a, byte[] b);
  1430.     private static native byte[][] plumbDivideAndRemainder(byte[] a, byte[] b);
  1431.     private static native byte[] plumbGcd(byte[] a, byte[] b);
  1432.     private static native byte[] plumbModPow(byte[] a, byte[] b, byte[] m);
  1433.     private static native byte[] plumbModInverse(byte[] a, byte[] m);
  1434.     private static native byte[] plumbSquare(byte[] a);
  1435.     private static native byte[] plumbGeneratePrime(byte[] a);
  1436.  
  1437.     /** use serialVersionUID from JDK 1.1. for interoperability */
  1438.     private static final long serialVersionUID = -8287574255936472291L;
  1439.  
  1440.     /**
  1441.      * Reconstitute the <tt>BigInteger</tt> instance from a stream (that is,
  1442.      * deserialize it).
  1443.      */
  1444.     private synchronized void readObject(java.io.ObjectInputStream s)
  1445.         throws java.io.IOException, ClassNotFoundException {
  1446.         // Read in all fields
  1447.     s.defaultReadObject();
  1448.  
  1449.         // Defensively copy magnitude to ensure immutability
  1450.         magnitude = (byte[]) magnitude.clone();
  1451.  
  1452.         // Validate signum
  1453.     if (signum < -1 || signum > 1)
  1454.         throw new java.io.StreamCorruptedException(
  1455.                         "BigInteger: Invalid signum value");
  1456.     if ((magnitude.length==0) != (signum==0))
  1457.         throw new java.io.StreamCorruptedException(
  1458.                         "BigInteger: signum-magnitude mismatch");
  1459.  
  1460.         // Set "cached computation" fields to their initial values
  1461.         bitCount = bitLength = -1;
  1462.         lowestSetBit = firstNonzeroByteNum = -2;
  1463.     }
  1464. }
  1465.